class LRUCache {

    /**
    LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

    双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
    哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

    在双向链表的实现中，使用一个伪头部（dummy head）和伪尾部（dummy tail）标记界限，
    这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。
     */

    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode(){}
        public DLinkedNode(int _key,int _value) {
            key = _key;
            value = _value;
        }
    }

    private Map<Integer,DLinkedNode> map = new HashMap<Integer,DLinkedNode>();
    private int size;//大小
    private int capacity;//容量大小
    private DLinkedNode head,tail;//伪头部，伪尾部

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;//刚开始让两个伪节点建立双向链接
    }
    
    public int get(int key) {
        //先通过HashMap查看是否有key，找到他把他放在头，并且返回节点值
        DLinkedNode node = map.get(key);//先通过key查看这个节点
        if(node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;//返回节点值
    }
    
    public void put(int key, int value) {
        //先查看是否存在，如果不存在，先判断是否超出容量，有，删除最后一个，没有，创建一个新的节点放在头部
        //如果存在，更改节点值，并且将其放在头部
        DLinkedNode node = map.get(key);//先通过key查看这个节点
        if(node == null) {
            //不存在，创建一个新的节点
            DLinkedNode newNode = new DLinkedNode(key,value);
            map.put(key,newNode);//吧节点放到HashMap中
            addToHead(newNode);//吧节点放在头部
            ++size;//大小+1
            if(size > capacity) {
                //超出容量，删除尾节点
                DLinkedNode tail = removeTail();
                //删除HashMap中的对应向
                map.remove(tail.key);
                --size;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    private void removeNode(DLinkedNode node) {//使得node节点与前后断开联系，使他独立
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToHead(DLinkedNode node) {//使节点加到头部，head的之后
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;//找到尾节点
        removeNode(res);
        return res;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */